/*
 * @lc app=leetcode.cn id=802 lang=typescript
 *
 * [802] 找到最终的安全状态
 */

// @lc code=start
function isSafe(graph: number[][], color: number[], v: number): boolean {
  // 如果v在栈中，返回false，否则返回true
  if (color[v] > 0) return color[v] === 2;
  // 入栈
  color[v] = 1;
  for (const x of graph[v]) {
    // 如果x在栈中，表示在环上，非安全状态
    if (!isSafe(graph, color, x)) return false;
  }
  // 已经访问过了
  color[v] = 2;
  return true;
}

function eventualSafeNodes(graph: number[][]): number[] {
  const m = graph.length;
  const color = new Array(m).fill(0);
  const ans = [];
  // 每个结点都dfs，判断是否有环
  for (let i = 0; i < m; i++) {
    if (isSafe(graph, color, i)) {
      ans.push(i);
    }
  }

  return ans;
}
// @lc code=end
